# 给你一个字符串 s，找到 s 中最长的回文子串。（回文串是正序、倒序的值相同）
# 
# 示例 1：
# 输入：s = "babad"
# 输出："bab"
# 解释："aba" 同样是符合题意的答案。
# 示例 2：
# 输入：s = "cbbd"
# 输出："bb"
#  
# 提示：
# 	1 <= s.length <= 1000
# 	s 仅由数字和英文字母组成

class Solution:
    def findPalindrome(self, s, l, r):
        n = len(s)
        
        while l >=0 and r < n and s[l] == s[r]:
            l -= 1
            r += 1
        
        return l+1, r-1
    
    def longestPalindrome(self, s: str) -> str:
        n = len(s)
        l = n + 1
        r = -1
        
        for i in range(n):
            l1, r1 = self.findPalindrome(s, i, i)
            if r1 - l1 > r - l:
                l, r = l1, r1
            if i > 0 and s[i-1] == s[i]:
                l2, r2 = self.findPalindrome(s, i-1, i)
                if r2 - l2 > r - l:
                    l, r = l2, r2
        
        return s[l:r+1]
    
    
if __name__ == "__main__":
    so = Solution()
    print(1)
    print(so.longestPalindrome("babad"))
    print(2)
    print(so.longestPalindrome("cbbd"))
